1. Field of the Invention
The present invention relates to a trellis decoder of a DTV (Digital Television) and, more particularly, to a trellis decoder using Viterbi algorithm.
2. Discussion of Related Art
ATSC (Advanced Television Systems Committee) in America has determined to adopt 8VSB (Vestigial Sideband) as a transmission system, which employs a channel coding system comprising an R-S (Reed-Solomon) decoder and a trellis decoder using Viterbi algorithm as shown in FIG. 1.
A simple Viterbi encoding algorithm is described in the following example of a convolutional encoder whose encoding rate R is 1/2, constraint length K is 3, and generating polynomial expressions are given by G1=1+X+X.sup.2 and G2=1+X.sup.2.
As shown in FIG. 2, a convolutional encoder comprises a 2-bit shift register 1, and two adders 2 and 3 for performing modulo-two additions. The outputs G1 and G2 are dependent on the state and output of the shift register 1, as shown in a trellis diagram of the outputs with time in FIG. 3. In the diagram, each point represents the state of the shift register 1, branch of a solid line a transition with the input of 0, and branch of a dotted line a transition with the input of 1. The numerals on each branch indicate the output values G1 and G2 when a transition takes place in the branch.
As shown in FIG. 3, two paths are combined in each state. According to a Viterbi algorithm based on the maximum likelihood decoding system, the more likely one of the two paths is chosen but the other is ignored. This means that the smaller one of two path values is selected but the larger one is truncated.
Thus selected path is referred to as "survivor" and each state holds information concerning the path as much as a decision depth or truncation depth. The most likely path to each state is selected for the purpose of tracing it back to accomplish an decoding operation.
FIG. 4 shows a trellis decoder based on the Viterbi decoding algorithm. Referring to FIG. 4, the trellis decoder comprises a branch metric unit 11, an ACS (Add-Compare-Select) unit 12, a maximum likelihood value detector 13, a normalization unit 14, a path memory 15, a state metric memory 16, and a traceback unit 17.
The branch metric unit 11 operates a branch metric of received input signals and a reference value in each branch to subtract the maximum likelihood value from the output of the ACS unit 12. This makes it possible to hold a path metric value in a memory of low capacity. The path memory 15 stores information concerning the path in each state and the state metric memory 16 stores state metric values. The traceback unit 17 searches for a state having a smallest path metric value in the present stage to use it as an initial value. This value is used to control the path memory 15 and perform a traceback for the purpose of looking for the original input data devoid of errors.
The digital transmission system which is suggested for the ground control communication by ATSC employs an NTSC interference removing filter in addition to the above-described trellis decoder in order to maximize its service area.
The NTSC interference removing filter installed in a DTV receiver, as shown in FIG. 5, comprises a delay unit 21 for delaying an input signal, and a subtracter 22 for subtracting the output of the delay unit 21 from the input signal.
The NTSC interference removing filter is not always used but selectively used by the determination of the receiver according to the amount of NTSC co-channel interference. Because the NTSC interference removing filer is available with 1-D.sup.12 channels, it actually limits the use of the trellis decoder.
Therefore, to minimize the structure of the trellis decoder of a DTV receiver when the NTSC interference removing filter is used, the transmitter uses a trellis coding interleaving comprising twelve equivalent trellis encoders TE1 to TE12, and input/output selectors S1 and S2, as shown in FIG. 6. Instead of the trellis decoders D1 to TD12 of 1-D.sup.12 channels, the receiver comprises twelve equivalent trellis decoders TD1 to TD12 arranged in parallel, and input/output selectors S3 and S4, as shown in FIG. 7. As a result, the receiver can be realized by using twelve trellis decoders for 1-D channels with the reduction in the hardware costs and complexity of design.
To realize the trellis decoders in a DTV receiver of ATSC standards, it is required to use twelve equivalent trellis decoders having the construction as shown in FIG. 3. The use of twelve trellis decoders can make the design easier but results in the increase of cost for hardware.